package com.leetcode;


import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author wangruiyang <wangruiyang@kuaishou.com>
 * Created on 2024-03-26
 */
@SuppressWarnings("checkstyle:VisibilityModifier")
public class No2641 {

    /**
     * 给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。
     * 如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。
     * 请你返回修改值之后，树的根 root
     */
    public TreeNode replaceValueInTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.val = 0;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int sum = 0;
            for (TreeNode node : deque) {
                sum += (node.left != null ? node.left.val : 0);
                sum += (node.right != null ? node.right.val : 0);
            }

            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                int childSum = (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0);
                if (node.left != null) {
                    node.left.val = sum - childSum;
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    node.right.val = sum - childSum;
                    deque.offer(node.right);
                }
            }
        }
        return root;
    }
}
